import java.net.Inet4Address;
import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-10-06
 * Time: 15:42
 */
public class Main {
    public List<String> topKFrequent(String[] words, int k) {
        //先统计次数
        Map<String,Integer> map=new HashMap<>();
        for (String str:words) {
            if(map.containsKey(str)){
                int value=map.get(str);
                map.remove(str);
                map.put(str,value+1);
            }else{
                map.put(str,1);
            }
        }
        //建堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap=new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                //add时,为了让次数相同的字符串,按字母顺序更大的放进更前面
                //方便后来被替换掉
                if(o1.getValue().equals(o2.getValue())){
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue()-o2.getValue();
            }
        });
        //开始筛选
        Set<Map.Entry<String, Integer>> set=map.entrySet();
        for(Map.Entry<String,Integer> entry:set){
            if(minHeap.size()<k){
                minHeap.add(entry);
            }else{
                if(entry.getValue()>minHeap.peek().getValue()){
                    minHeap.poll();
                    minHeap.add(entry);
                }else if(entry.getValue().equals(minHeap.peek().getValue())){
                    if(entry.getKey().compareTo(minHeap.peek().getKey())<0){
                        minHeap.poll();
                        minHeap.add(entry);
                    }
                }
            }
        }
        List<String> list=new ArrayList<>();
        //注意minHeap的大小一直在变,所以不能是minHeap.size()
        //应该为k
        for(int i=0;i<k;i++){
            list.add(minHeap.poll().getKey());
        }
        Collections.reverse(list);
        return list;
    }
}
